


class Solution:
    def letterCombination(self, digits):

        if len(digits) == 0:
            return []
        
        # 号码对应表
        phone = {
            '2': ['a', 'b', 'c'],
            '3': ['d', 'e', 'f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            "6": ['m', 'n', 'o'],
            "7": ['p', 'q', 'r', 's'],
            "8": ['t', 'u', 'v'],
            "9": ['w', 'x', 'y', 'z']
        }

        def backtrack(conbination, nextdigit):
            
            if len(nextdigit) == 0:
                res.append(conbination)

            else:
                for letter in phone[nextdigit[0]]:

                    backtrack(conbination + letter, nextdigit[1:])


        res = []
        backtrack("", digits)

        return res





if __name__ == "__main__":
    
    digits = "232"

    sol = Solution()
    res = sol.letterCombination(digits)
    print(res)

